#include <iostream>
#include <stdbool.h>
#include <assert.h>
#include <list>
#include <algorithm>
using namespace std;
namespace wanghao
{
    template<class T>
    struct list_node
    {
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;

        //全缺省构造
        list_node(const T& x = T())
            :_data(x)
            ,_next(nullptr)
            ,_prev(nullptr)
        {}
    };
    //普通迭代器类
    template<class T,class Ref,class Ptr>
    struct list_itarator
    {
        typedef list_node<T> Node;
        typedef list_itarator<T,Ref,Ptr> Self;
        Node* _node;
        list_itarator(Node* node)
            :_node(node)
        {}
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Self operator++(int)
        {
            Self tmp(*this);
            _node = _node->_next;
            return tmp;
        }
        Self operator--(int)
        {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }
        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }
        bool operator==(const Self& s)
        {
            return _node == s._node;
        }

    };
    //const迭代器类
    // template<class T>
    // struct list_const_itarator
    // {
    //     typedef list_node<T> Node;
    //     typedef list_const_itarator<T> Self;
    //     Node* _node;
    //     list_const_itarator(Node* node)
    //         :_node(node)
    //     {}
    //     const T& operator*()
    //     {
    //         return _node->_data;
    //     }
    //     const T* operator->()
    //     {
    //         return &_node->_data;
    //     }
    //     Self& operator++()
    //     {
    //         _node = _node->_next;
    //         return *this;
    //     }
    //     Self& operator--()
    //     {
    //         _node = _node->_prev;
    //         return *this;
    //     }
    //     Self operator++(int)
    //     {
    //         Self tmp(*this);
    //         _node = _node->_next;
    //         return tmp;
    //     }
    //     Self operator--(int)
    //     {
    //         Self tmp(*this);
    //         _node = _node->_prev;
    //         return tmp;
    //     }
    //     bool operator!=(const Self& s)
    //     {
    //         return _node != s._node;
    //     }

    // };
    template<class T>
    class list
    {
        typedef list_node<T> Node;
    public:
        // typedef list_itarator<T > iterator;
        // typedef list_const_itarator<T> const_iterator;
        typedef list_itarator<T,T&,T* > iterator;
        typedef list_itarator<T,const T&,const T* > const_iterator;
        //迭代器
        iterator begin()
        {
            return iterator(_head->_next);
        }
        iterator end()
        {
            return iterator(_head);
        }
        const_iterator begin() const
        {
            return const_iterator(_head->_next);
        }
        const_iterator end() const
        {
            return const_iterator(_head);
        }
        void enmty_init()
        {
            _head = new Node();
            _head->_next = _head;
            _head->_prev = _head;
            _size = 0;
        }
        //无参构造
        list()
        {
            enmty_init();
        }
        //n个val构造
        list(size_t n,const T& val = T())
        {
            enmty_init();
            for(int i = 0;i < n;i++)
            {
                push_back(val);
            }
        }
        //initializer_list构造
        list (initializer_list<T> il)
        {
            enmty_init();
            for(auto& e : il)
            {
                push_back(e);
            }
        }
        //拷贝构造
        list(const list<T>& l)
        {
            enmty_init();
            for(auto& e : l)
            {
                push_back(e);
            }
        }
        //交换
        void swap(list<T>& l)
        {
            std::swap(_head,l._head);
            std::swap(_size,l._size);
        }
        //赋值重载
        //list<T>& operator=(list<T> l)
        //类里面可以不加模板参数,类外面就不行了,但是还是建议加上
        list& operator=(list l)
        {
            swap(l);
            return *this;
        }
        //析构
        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }
        void clear()
        {
            //值全部删掉,哨兵位的头结点不动
            list<T>::iterator it = begin();
            while(it != end())
            {
                it = erase(it);
            }
        }
        //尾插
        void push_back(const T& val)
        {
            // Node* new_node = new Node(val);
            // Node* ptail = _head->_prev;

            // ptail->_next = new_node;
            // new_node->_prev = ptail;

            // new_node->_next = _head;
            // _head->_prev = new_node;
            insert(end(),val);
        }
        //头插
        void push_front(const T& val)
        {
            insert(begin(),val);
        }
        //尾删
        void pop_back()
        {
            assert(begin() != end());
            erase(--end());
        }
        //头删
        void pop_front()
        {
            assert(begin() != end());
            erase(begin());
        }
        size_t size()
        {
            return _size;
        }
        //指定位置插入
        iterator insert (iterator pos, const T& val = T())
        {
            //当前节点
            Node* cur = pos._node;
            //申请节点
            Node* new_node = new Node(val);
            //前一个节点
            Node* prev = cur->_prev;

            prev->_next = new_node;
            new_node->_next = cur;
            cur->_prev = new_node;
            new_node->_prev = prev;
            ++_size;
            return iterator(new_node);
        }
        //指定位置删除
        //erase有迭代器失效
        iterator erase (iterator pos)
        {
            assert(pos != end());
            //当前结点
            Node* del = pos._node;
            //找到前一个结点
            Node* prev = del->_prev;
            //找到后一个结点
            Node* next = del->_next;
            //链接
            prev->_next = next;
            next->_prev = prev;
            delete del;
            del = nullptr;
            --_size;
            return iterator(next);
        }
        
    private:
        Node* _head;
        size_t _size;
    };
    template<class T>
    void swap(list<T>& l1,list<T>& l2)
    {
        l1.swap(l2);
    }
}